
package com.liwt.algorithm;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 双队列实现栈
 * 
 * @author likebamboo
 * @create 2013-10-21
 * @see http://blog.csdn.net/likebamboo/article/details/12906747
 * @param <E>
 */
public class MyStack<E> {
    /**
     * 队列A
     */
    private Queue<E> qA;

    /**
     * 队列B
     */
    private Queue<E> qB;

    public MyStack() {
        super();
        qA = new LinkedList<E>();
        qB = new LinkedList<E>();
    }

    /**
     * 入栈操作
     * 
     * @param item
     */
    public void push(E item) {
        // 如果B队列不为空,将元素入B队列
        if (!qB.isEmpty()) {
            qB.offer(item);
            return;
        }
        // 如果两个队列均为空，或者A队列不为空，均将原始加入A队列
        qA.offer(item);
    }

    /**
     * 出栈操作
     * 
     * @return
     */
    public E pop() {
        // 如果队列B不为空，那么将B队列中的前N-1个元素出队并进入A队。
        // 并将B队列中的最后一个元素出队列并返回。
        if (!qB.isEmpty()) {
            while (qB.size() > 1) {
                qA.offer(qB.poll());
            }
            return qB.poll();
        }

        // 如果队列B为空，那么不管A队列是否为空(为空时抛出异常也是合理的).
        // 将A队列中前N-1个元素出队并进入A队列。再返回A队列中的最后一个元素。
        while (qA.size() > 1) {
            qB.offer(qA.poll());
        }
        return qA.poll();
    }

    /**
     * 栈是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return qA.isEmpty() && qB.isEmpty();
    }

    public static void main(String[] args) {
        MyStack<String> stack = new MyStack<String>();
        stack.push("first");
        System.out.println(stack.pop());
        stack.push("second");
        stack.push("third");
        stack.push("forth");
        stack.push("fifth");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }
}
